package leetcode.code1690;

import leetcode.IDebug;
import leetcode.helper.H;

class Solution10 implements IDebug {
	// 所以就是这个结构
	public Integer[][] dp1;
	public Integer[][] dp2;

	public int stoneGameVII(int[] stones) {
		int len = stones.length;
		int[] sums = new int[len + 1];
		for (int i = 1; i < sums.length; i++) {
			sums[i] = sums[i - 1] + stones[i - 1];
		}
		// dp[a][b][c][0] = -1，表示：
		// (a,b,c)这个状态没算过
		dp1 = new Integer[len][len];
		dp2 = new Integer[len][len];
		alice(stones, sums, 0, len - 1);
		return dp1[0][len - 1];
	}

	public void alice(int[] stones, int[] sums, int l, int r) {
		if (dp1[l][r] != null) {
			return;
		}
		if (l + 1 == r) {
			if (stones[l] <= stones[r]) {
				dp1[l][r] = stones[r];
			} else {
				dp1[l][r] = stones[l];
			}
		} else {
			bob(stones, sums, l + 1, r);
			int ans10 = dp2[l + 1][r] + sums[r + 1] - sums[l + 1];
			bob(stones, sums, l, r - 1);
			int ans20 = dp2[l][r - 1] + sums[r] - sums[l];
			if (ans10 >= ans20) {
				dp1[l][r] = ans10;
			} else {
				dp1[l][r] = ans20;
			}
		}
	}

	public void bob(int[] stones, int[] sums, int l, int r) {
		if (dp2[l][r] != null) {
			return;
		}
		if (l + 1 == r) {
			if (stones[l] <= stones[r]) {
				dp2[l][r] = -stones[r];
			} else {
				dp2[l][r] = -stones[l];
			}
		} else {
			alice(stones, sums, l + 1, r);
			int ans11 = dp1[l + 1][r] - sums[r + 1] + sums[l + 1];
			alice(stones, sums, l, r - 1);
			int ans21 = dp1[l][r - 1] - sums[r] + sums[l];
			if ( ans11 >= ans21) {
				dp2[l][r] = ans21;
			} else {
				dp2[l][r] = ans11;
			}
		}
	}

	@Override
	public void debug4() {
		H.compare(6, this.stoneGameVII(H.str2array3("[5,3,1,4,2]")));
//		H.compare(122, this.stoneGameVII(H.str2array3("[7,90,5,1,100,10,10,2]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution10 so = new Solution10();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		char c = '\u0000';
//		System.out.println(c==d);
//		System.out.println('\u0020'==' ');
//		System.out.println(d==' ');
//		System.out.println(c==' ');
//		System.out.println(c==(char)32);
//		System.out.println((char)32);
	}
}